1. Field of the Invention
The present invention is generally related to the graphical rendering of image data over surfaces defined by polygon meshes and, in particular, to a system and methods of efficiently regularizing a polygon mesh having multiple tessellation levels to support image parcel texture rendering without visual T-junction artifacts.
2. Description of the Related Art
Substantial advances have been mode in the computer-based algorithms for rendering surface textures over complex manifolds to obtain visually realistic presentations of graphic images. Conventional, image data-set processing techniques permit the generation of photo-realistic views of objects within virtual environments embodying multiple radiosity sources and correspondingly complex shading patterns.
There are, however, several known problems with conventional image data-set processing and rendering algorithms, particularly where the image processing is desirably performed to provide real-time or near real-time rendering of the image in support of visual interactivity with the continuously displayed image. These problems include various types of data degeneracies and discontinuities introduced by the origin and nature of the source image data. Other problems arise from the dynamic processing of image data sets in support of real-time rendering of the image, which produce defects or voids in the topological surface of the displayed image. Such defects, directly perceived as visual artifacts in the image, are of particular significance, since the existence of a uniform manifold is typically presumed for conventional radiosity, shading, and similar algorithms. A radiosity error arising from even a small topological defect can greatly amplify the perceptual significance of the defect and significantly compromise the visual value of the displayed image.
Real-time and near real-time image presentation algorithms often employ a multi-resolution hierarchy generation scheme to optimize the perceptual value of the displayed image. Image parcels are displayed at different resolutions in a manner that correlates the level of detail of different image parcels with the perceptual significance of the informational content of the parcels. In general, image parcels of that appear closer to the image view point are considered to have a higher relevant informational content and are therefore desirably rendered with a higher resolution. Image parcels virtually further from the image view point are displayed variously with lower resolutions, thereby reducing computational complexities associated with the rendering process and in turn enhancing the real-time or near real time display of the image.
Conventionally, image parcels are rendered using various texture mapping algorithms based on polygonal meshes used to topologically define the image surface. The discrete vertices of the polygonal mesh are established in a regular distribution over an image parcel map based on some typically non-linear height function, such as a digital elevation mode (DEM) function, derived from the image data. Image parcels, correlated to locations within the image parcel map, are texture mapped into overlying mesh polygons to render the corresponding portion of the image surface.
Irregularities in a polygonal mesh, leading to the occurrence of surface defects, can be introduced from multiple sources, including variances and discontinuities in the source image data and the various algorithms used to define the mesh. Topology and geometry simplification algorithms variously employed to improve the perceived quality of the displayed image and to regularize the image data to reduce the computational complexity of image data rendering can also create mesh irregularities. Mesh irregularities can also be introduced through the generalized rendering process, such as when using multi-resolution hierarchy display process.
Polygonal mesh irregularities generally result in image defects, usually referred to as cracks, that occur due to the imperfect alignment of mesh vertices. Mis-alignments result in the evaluation of different height function values along the opposing boarders of adjacent image parcels. Depending on the current image projection angle, the rendering of the adjacent image parcels based on the mis-aligned adjacent polygons leaves a visible topological void in the image surface.
In the particular case of multi-resolution images, cracks commonly if not all too frequently occur on the polygon mesh boarders between image parcels of different resolutions. The dissimilar intervals between mesh vertices frequently results in the occurrence of T-junctions, defined as the occurrence of a boarder vertex in a higher resolution mesh dissociated from any corresponding boarder vertex in the lower-resolution mesh. Again depending on the image projection angle, a crack occurs due to the difference in the height function evaluated along the bordering image parcel polygons, typically with a maximum associated with the T-junction vertex.
The correction of image defects, such as arising from T-junction cracks, is necessary to preserve the integrity and visual realism of a displayed image. Efficient correction is also required to maintain the capability to perform real-time image presentation and interactive manipulation of the image. Different algorithms have been proposed and variously implemented to correct image defects, including cracks, systematically or by detecting, categorizing, and specifically correcting the underlying image data.
In Topology Simplification for Polygonal Virtual Environments, Jihad El-Sana and Amitabh Varshney, IEEE Trans. Visualization and Computer Graphics, 4(2):133-144, April-June 1998, a genus algorithmic approach to implementing topological simplifications for removing holes and protuberances is described. The approach implements the conceptual sweeping of an α-shape over an image corresponding polygonal mesh and processing the underlying image data to selectively add and remove data triangulations that variously correspond to the filling of topological holes and smoothing of topological protuberances.
Conventional boundary-oriented approaches to categorizing and correcting image defects variously attempt to re-fit mesh irregularities that represent voids by variously shifting vertices to merge boundaries and clustering vertices, including merging pairs of vertices, that are within some defined error range. In Consistent Solid and Boundary Representations from Arbitrary Polygonal Data, Murali, T. M. and Thomas A. Funkhouser, Proceedings of 1997 Symposium on Interactive 3D Graphics. April 27-30. pp. 155-162, 196, a solid modeling approach is described that evaluates the image data to develop a set of solid regions that are in turn used to generate a correct triangulation enclosing the solid regions, thereby providing a correct basis for defining a topological surface necessary to close a void with a correct orientation. Still other algorithms propose various numerical approximation and curve fitting algorithms operating over the image data to support the addition of multiple polygons to fill simple to complex void forms.
In general, however, all of these conventional approaches tend to be highly compute intensive and tend to require a significant evaluation of the underlying image data. In circumstances where a high degree of interactivity is desired, particularly where the available computing resources may be limited, use of such conventional approaches may limit the perceived quality of the rendered image or reduce interactive response to qualitatively undesirable levels.
Given the ever increasing pervasiveness of computing through portable and appliance devices, there is a clear desire to maintain if not improve the image quality and interactively achievable in connection with the rendering of topological surfaces, particularly where computer performance and memory resources may be limited.